Title: Dolev-Yao theories for distributive encryption

Speaker: A. Baskar


Abstract:
 In the context of modeling cryptographic tools like blind signatures and
homomorphic encryption, the Dolev-Yao model is typically extended with an
operator over which encryption is distributive. We consider one such
theory which lacks any obvious locality property and show that its
derivability problem is hard: in fact, it is dexptime-complete, and there
is an exponential lower bound on the size of derivations. The lower bound
contrasts with ptime decidability for restricted theories of blind
signatures, and the upper bound with non-elementary decidability for
abelian group operators with distributive encryption.